import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Consumer;

import lombok.Getter;

/**
 * @author xhw
 */

@Getter
class TreeNode {
    private Object val;
    private List<TreeNode> children;

    public TreeNode(Object val) {
        this.val = val;
        this.children = new ArrayList<>();
    }

    public void addChild(TreeNode child) {
        children.add(child);
    }

}

class Tree {
    // 定义一个根节点
    public TreeNode root;

    // 广度优先搜索
    public void breadthFirstSearch(Consumer<TreeNode> action) {
        if (root == null) {
            return;
        }

        LinkedList<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);

        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();
            action.accept(node);

            nodes.addAll(node.getChildren());
        }

    }

    // 深度优先搜索
    public void depthFirstSearch(TreeNode node, Consumer<TreeNode> action) {
        if (node != null) {
            action.accept(node); // 对当前节点执行操作
            node.getChildren().forEach(child -> depthFirstSearch(child, action)); // 递归遍历子节点
        }
    }

    // 遍历所有子节点获取树的高度
    public int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            int height = 0;
            for (TreeNode child : node.getChildren()) {
                height = Math.max(height, getHeight(child));
            }
            // 加1表示当前节点的高度
            return height + 1;
        }
    }

}

public class 遍历树 {
    public static void main(String[] args) {
        Tree tree = new Tree();
        TreeNode root = new TreeNode("root");
        TreeNode child1 = new TreeNode("ch1");
        TreeNode child2 = new TreeNode("ch2");
        TreeNode child1_1 = new TreeNode("ch1_1");
        TreeNode child1_2 = new TreeNode("ch1_2");
        TreeNode child2_1 = new TreeNode("ch2_1");
        TreeNode child2_2 = new TreeNode("ch2_2");

        root.addChild(child1);
        root.addChild(child2);
        child1.addChild(child1_1);
        child1.addChild(child1_2);
        child2.addChild(child2_1);
        child2.addChild(child2_2);

        tree.root = root;

        System.out.println("广度优先搜索");
        tree.breadthFirstSearch(node -> System.out.print(node.getVal() + " "));

        System.out.println("");

        System.out.println("深度优先搜索");
        tree.depthFirstSearch(root, node -> System.out.print(node.getVal() + " "));

    }
}